package com.javabasic.algorithm.leetcode;

import java.util.LinkedList;

public class ValidParentheses {

    public boolean isValid(String s) {
        if (s == null || "".equals(s)) return true;
        LinkedList<Character> stack = new LinkedList<>();
        int len = s.length();
        for (int i = 0; i < len; i++) {
            if (s.charAt(i) == ']') {
                if (stack.isEmpty() == false && stack.getLast() == '[') {
                    stack.removeLast();
                } else {
                    return false;
                }
            } else if (s.charAt(i) == ')') {
                if (stack.isEmpty() == false && stack.getLast() == '{') {
                    stack.removeLast();
                } else {
                    return false;
                }
            } else if (s.charAt(i) == '}') {
                if (stack.isEmpty() == false && stack.getLast() == '(') {
                    stack.removeLast();
                } else {
                    return false;
                }
            } else {
                stack.add(s.charAt(i));
            }

        }
        return stack.size() == 0?true:false;
    }
}
